// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssa

import (
	"cmd/internal/src"
	"fmt"
	"math"
)

type branch int

const (
	unknown branch = iota
	positive
	negative
)

// 关系表示变量对（v，w）之间可能存在的一组关系。在没有先验知识的情况下，
// 掩码是lt | eq | gt，意思是v可以小于、等于或
// 大于w。当执行路径在条件
// /`v op w`上分支时，关系集被更新，以排除任何由于'v op w`为真（或假）而不可能存在的
// 关系。
// 
// 例如
// 
// r:=关系（…）
// 
// if v<w{
// newR:=r&lt 
// }
// if v>=w{
// newR:=r&（eq | gt）
// }
// if v=w{
// newR:=r&（lt|gt）
// }
type relation uint

const (
	lt relation = 1 << iota
	eq
	gt
)

var relationStrings = [...]string{
	0: "none", lt: "<", eq: "==", lt | eq: "<=",
	gt: ">", gt | lt: "!=", gt | eq: ">=", gt | eq | lt: "any",
}

func (r relation) String() string {
	if r < relation(len(relationStrings)) {
		return relationStrings[r]
	}
	return fmt.Sprintf("relation(%d)", uint(r))
}

// /域表示变量对的域，其中已知一组
// 关系。例如，为无符号
// 对学习的关系不能传输到有符号对，因为同一位
// 表示可能意味着其他内容。
type domain uint

const (
	signed domain = 1 << iota
	unsigned
	pointer
	boolean
)

var domainStrings = [...]string{
	"signed", "unsigned", "pointer", "boolean",
}

func (d domain) String() string {
	s := ""
	for i, ds := range domainStrings {
		if d&(1<<uint(i)) != 0 {
			if len(s) != 0 {
				s += "|"
			}
			s += ds
			d &^= 1 << uint(i)
		}
	}
	if d != 0 {
		if len(s) != 0 {
			s += "|"
		}
		s += fmt.Sprintf("0x%x", uint(d))
	}
	return s
}

type pair struct {
	v, w *Value // 一对值，按ID排序。
	// v可以为零，表示零值。
	// 对于布尔型，零值（v==nil）为假。
	d domain
}

// 事实是一对加上该对的关系。
type fact struct {
	p pair
	r relation
}

// a limit记录一个值的已知上限和下限。
type limit struct {
	min, max   int64  // min<=value<=max，有符号
	umin, umax uint64 // umin<=value<=umax，无符号
}

func (l limit) String() string {
	return fmt.Sprintf("sm,SM,um,UM=%d,%d,%d,%d", l.min, l.max, l.umin, l.umax)
}

func (l limit) intersect(l2 limit) limit {
	if l.min < l2.min {
		l.min = l2.min
	}
	if l.umin < l2.umin {
		l.umin = l2.umin
	}
	if l.max > l2.max {
		l.max = l2.max
	}
	if l.umax > l2.umax {
		l.umax = l2.umax
	}
	return l
}

var noLimit = limit{math.MinInt64, math.MaxInt64, 0, math.MaxUint64}

// limitFact是一个已知特定值的极限。
type limitFact struct {
	vid   ID
	limit limit
}

// factsTable跟踪值对之间的关系。
// 
// 事实表逻辑是合理的，但不完整。除了少数
// 特殊情况外，它不执行演绎或算术运算。虽然有已知的决策过程，但事实表采用的特别方法对实际代码有效，同时保持非常高效。
type factsTable struct {
	// 如果事实包含矛盾，unsat是正确的。注意factsTable逻辑是不完整的，因此如果unsat 
	// 为假，factsTable中的断言可能是可满足的或不可满足的。
	unsat      bool // 如果事实包含矛盾，则为true 
	unsatDepth int  // 未设置检查点的数量

	facts map[pair]relation // 当前已知的关系集
	stack []fact            // 以前的关系集

	// 顺序是一对偏序集，记录有符号和无符号
	// 
	orderS *poset
	orderU *poset

	// 单个值的已知上下限。
	limits     map[ID]limit
	limitStack []limitFact // 之前的条目

	// 对于每个切片，从s到len（s）/cap（s）值（如果有）的映射
	// TODO：检查是否存在与我们的切片有多个len（s）有关的情况。如有必要，我们可以保留一份清单。
	lens map[ID]*Value
	caps map[ID]*Value

	// 零是一个零值常量
	zero *Value
}

// checkpointFact是一个无效值，用于检查
// 和恢复factsTable。
var checkpointFact = fact{}
var checkpointBound = limitFact{}

func newFactsTable(f *Func) *factsTable {
	ft := &factsTable{}
	ft.orderS = f.newPoset()
	ft.orderU = f.newPoset()
	ft.orderS.SetUnsigned(false)
	ft.orderU.SetUnsigned(true)
	ft.facts = make(map[pair]relation)
	ft.stack = make([]fact, 4)
	ft.limits = make(map[ID]limit)
	ft.limitStack = make([]limitFact, 4)
	ft.zero = f.ConstInt64(f.Config.Types.Int64, 0)
	return ft
}

// 更新更新域d中v和w之间的关系集
// 将其限制为r。
func (ft *factsTable) update(parent *Block, v, w *Value, d domain, r relation) {
	if parent.Func.pass.debug > 2 {
		parent.Func.Warnl(parent.Pos, "parent=%s, update %s %s %s", parent, v, w, r)
	}
	// 如果我们已经找到unsat，则无需执行任何其他操作。
	if ft.unsat {
		return
	}

	// 自我事实。将其注册到facts 
	// 表中是浪费的，所以只需注意它是否令人满意
	if v == w {
		if r&eq == 0 {
			ft.unsat = true
		}
		return
	}

	if d == signed || d == unsigned {
		var ok bool
		order := ft.orderS
		if d == unsigned {
			order = ft.orderU
		}
		switch r {
		case lt:
			ok = order.SetOrder(v, w)
		case gt:
			ok = order.SetOrder(w, v)
		case lt | eq:
			ok = order.SetOrderOrEqual(v, w)
		case gt | eq:
			ok = order.SetOrderOrEqual(w, v)
		case eq:
			ok = order.SetEqual(v, w)
		case lt | gt:
			ok = order.SetNonEqual(v, w)
		default:
			panic("unknown relation")
		}
		if !ok {
			if parent.Func.pass.debug > 2 {
				parent.Func.Warnl(parent.Pos, "unsat %s %s %s", v, w, r)
			}
			ft.unsat = true
			return
		}
	} else {
		if lessByID(w, v) {
			v, w = w, v
			r = reverseBits[r]
		}

		p := pair{v, w, d}
		oldR, ok := ft.facts[p]
		if !ok {
			if v == w {
				oldR = eq
			} else {
				oldR = lt | eq | gt
			}
		}
		// 与facts表中已有的信息相比没有变化。
		if oldR == r {
			return
		}
		ft.stack = append(ft.stack, fact{p, oldR})
		ft.facts[p] = oldR & r
		// 如果此关系不可满足，请标记它并立即退出
		if oldR&r == 0 {
			if parent.Func.pass.debug > 2 {
				parent.Func.Warnl(parent.Pos, "unsat %s %s %s", v, w, r)
			}
			ft.unsat = true
			return
		}
	}

	// 在与常量
	if v.isGenericIntConst() {
		v, w = w, v
		r = reverseBits[r]
	}
	if v != nil && w.isGenericIntConst() {
		// 进行比较时提取边界注意：下面所有的+1/-1都可能溢出/下溢。
		// 两者都会产生正确的结果，这只会导致不精确。
		// 事实上，如果存在溢出/下溢，则无法访问相应的
		// 代码，因为已知范围超出了值类型的范围
		// 。
		old, ok := ft.limits[v.ID]
		if !ok {
			old = noLimit
			if v.isGenericIntConst() {
				switch d {
				case signed:
					old.min, old.max = v.AuxInt, v.AuxInt
					if v.AuxInt >= 0 {
						old.umin, old.umax = uint64(v.AuxInt), uint64(v.AuxInt)
					}
				case unsigned:
					old.umin = v.AuxUnsigned()
					old.umax = old.umin
					if int64(old.umin) >= 0 {
						old.min, old.max = int64(old.umin), int64(old.umin)
					}
				}
			}
		}
		lim := noLimit
		switch d {
		case signed:
			c := w.AuxInt
			switch r {
			case lt:
				lim.max = c - 1
			case lt | eq:
				lim.max = c
			case gt | eq:
				lim.min = c
			case gt:
				lim.min = c + 1
			case lt | gt:
				lim = old
				if c == lim.min {
					lim.min++
				}
				if c == lim.max {
					lim.max--
				}
			case eq:
				lim.min = c
				lim.max = c
			}
			if lim.min >= 0 {
				// int（x）>=0&&int（x）>=N⇒  uint（x）>=N 
				lim.umin = uint64(lim.min)
			}
			if lim.max != noLimit.max && old.min >= 0 && lim.max >= 0 {
				// 0<=int（x）<=N⇒  0<=uint（x）<=N 
				// 这是一个最大更新，所以下限
				// 来自我们已经知道的（旧）。
				lim.umax = uint64(lim.max)
			}
		case unsigned:
			uc := w.AuxUnsigned()
			switch r {
			case lt:
				lim.umax = uc - 1
			case lt | eq:
				lim.umax = uc
			case gt | eq:
				lim.umin = uc
			case gt:
				lim.umin = uc + 1
			case lt | gt:
				lim = old
				if uc == lim.umin {
					lim.umin++
				}
				if uc == lim.umax {
					lim.umax--
				}
			case eq:
				lim.umin = uc
				lim.umax = uc
			}
			// 我们可以使用
			// 符号含义的反作用来推导符号事实，但事实证明这无关紧要。
		}
		ft.limitStack = append(ft.limitStack, limitFact{v.ID, old})
		lim = old.intersect(lim)
		ft.limits[v.ID] = lim
		if v.Block.Func.pass.debug > 2 {
			v.Block.Func.Warnl(parent.Pos, "parent=%s, new limits %s %s %s %s", parent, v, w, r, lim.String())
		}
		if lim.min > lim.max || lim.umin > lim.umax {
			ft.unsat = true
			return
		}
	}

	// 下面的推导事实只与数字有关。
	if d != signed && d != unsigned {
		return
	}

	// 考虑到len和cap之间的关系，我们知道的其他事实。
	// 
	// TODO:既然现在证明派生了传递关系，那么只要知道在证明的开始处len（w）<=cap（w）就足够了，在这里我们寻找所有len/cap运算。
	if v.Op == OpSliceLen && r&lt == 0 && ft.caps[v.Args[0].ID] != nil {
		// len（s）>w表示封顶>w 
		// len（s）>=w表示封顶>=w 
		// len（s）==w表示封顶>=w 
		ft.update(parent, ft.caps[v.Args[0].ID], w, d, r|gt)
	}
	if w.Op == OpSliceLen && r&gt == 0 && ft.caps[w.Args[0].ID] != nil {
		// RHS上的长度相同。
		ft.update(parent, v, ft.caps[w.Args[0].ID], d, r|lt)
	}
	if v.Op == OpSliceCap && r&gt == 0 && ft.lens[v.Args[0].ID] != nil {
		// cap（s）<w表示len（s）<w 
		// cap（s）<=w表示len（s）<=w 
		// cap（s）==w表示len（s）<=w 
		ft.update(parent, ft.lens[v.Args[0].ID], w, d, r|lt)
	}
	if w.Op == OpSliceCap && r&lt == 0 && ft.lens[w.Args[0].ID] != nil {
		// RHS上的容量相同。
		ft.update(parent, v, ft.lens[w.Args[0].ID], d, r|gt)
	}

	// 过程栅栏柱影响。
	// 
	// 首先，使条件>或>=。
	if r == lt || r == lt|eq {
		v, w = w, v
		r = reverseBits[r]
	}
	switch r {
	case gt:
		if x, delta := isConstDelta(v); x != nil && delta == 1 {
			// x+1>w⇒  x>=w 
			// 
			// 这有助于消除append的
			// growtslice分支。
			ft.update(parent, x, w, d, gt|eq)
		} else if x, delta := isConstDelta(w); x != nil && delta == -1 {
			// v>x-1⇒  v>=x 
			ft.update(parent, v, x, d, gt|eq)
		}
	case gt | eq:
		if x, delta := isConstDelta(v); x != nil && delta == -1 {
			// x-1>=w&&x>min⇒  x>w 
			// 
			// 对i>0有用；s[i-1]。
			lim, ok := ft.limits[x.ID]
			if ok && ((d == signed && lim.min > opMin[v.Op]) || (d == unsigned && lim.umin > 0)) {
				ft.update(parent, x, w, d, gt)
			}
		} else if x, delta := isConstDelta(w); x != nil && delta == 1 {
			// v>=x+1&&x<max⇒  v>x 
			lim, ok := ft.limits[x.ID]
			if ok && ((d == signed && lim.max < opMax[w.Op]) || (d == unsigned && lim.umax < opUMax[w.Op])) {
				ft.update(parent, v, x, d, gt)
			}
		}
	}

	// 进程：x+delta>w（带delta常量）
	// 目前仅用于有符号域（用于访问循环中的切片）。
	if r == gt || r == gt|eq {
		if x, delta := isConstDelta(v); x != nil && d == signed {
			if parent.Func.pass.debug > 1 {
				parent.Func.Warnl(parent.Pos, "x+d %s w; x:%v %v delta:%v w:%v d:%v", r, x, parent.String(), delta, w.AuxInt, d)
			}
			if !w.isGenericIntConst() {
				// 如果我们知道x+delta>w，但w不是常数，我们可以推导：
				// 如果delta<0和x>MinInt-delta，那么x>w（因为x+delta不能下溢）
				// 这对边界为“len（slice）-K”（delta=-K）
				if l, has := ft.limits[x.ID]; has && delta < 0 {
					if (x.Type.Size() == 8 && l.min >= math.MinInt64-delta) ||
						(x.Type.Size() == 4 && l.min >= math.MinInt32-delta) {
						ft.update(parent, x, w, signed, r)
					}
				}
			} else {
				// 有了w，delta常数，我们想要推导：x+delta>w⇒  x>w-delta-
				// 
				// 我们计算（使用正确大小的整数）：
				// min=w-delta-
				// max=MaxInt-delta-
				// 
				// 我们证明：如果min<max:min<x和x<=max-
				// 
				// 即使在溢出的情况下，这也是正确的。
				// 
				// 如果初始事实是x+delta>=w，则派生条件是：
				// 如果min<max:min<=x和x<=max 
				// 如果min>max:min<=x或x<=max 
				// 
				// 注意max的条件仍然是<=，因为它们处理溢出。
				var min, max int64
				var vmin, vmax *Value
				switch x.Type.Size() {
				case 8:
					min = w.AuxInt - delta
					max = int64(^uint64(0)>>1) - delta

					vmin = parent.NewValue0I(parent.Pos, OpConst64, parent.Func.Config.Types.Int64, min)
					vmax = parent.NewValue0I(parent.Pos, OpConst64, parent.Func.Config.Types.Int64, max)

				case 4:
					min = int64(int32(w.AuxInt) - int32(delta))
					max = int64(int32(^uint32(0)>>1) - int32(delta))

					vmin = parent.NewValue0I(parent.Pos, OpConst32, parent.Func.Config.Types.Int32, min)
					vmax = parent.NewValue0I(parent.Pos, OpConst32, parent.Func.Config.Types.Int32, max)

				default:
					panic("unimplemented")
				}

				if min < max {
					// 记录x>min和max>=x 
					ft.update(parent, x, vmin, d, r)
					ft.update(parent, vmax, x, d, r|eq)
				} else {
					// 我们知道x>min或x<=max.factsTable不能记录或条件，
					// 所以让我们看看我们是否已经可以证明其中一个是假的，在这种情况下
					// 另一个必须是真的
					if l, has := ft.limits[x.ID]; has {
						if l.max <= min {
							if r&eq == 0 || l.max < min {
								// x>min（x>=min）是不可能的，所以它必须是x<=max 
								ft.update(parent, vmax, x, d, r|eq)
							}
						} else if l.min > max {
							// x<=max是不可能的，所以它必须是x>min 
							ft.update(parent, x, vmin, d, r)
						}
					}
				}
			}
		}
	}

	// 查看保值扩展。
	// 如果域适合预扩展类型，
	// 使用预扩展值重复更新。
	if isCleanExt(v) {
		switch {
		case d == signed && v.Args[0].Type.IsSigned():
			fallthrough
		case d == unsigned && !v.Args[0].Type.IsSigned():
			ft.update(parent, v.Args[0], w, d, r)
		}
	}
	if isCleanExt(w) {
		switch {
		case d == signed && w.Args[0].Type.IsSigned():
			fallthrough
		case d == unsigned && !w.Args[0].Type.IsSigned():
			ft.update(parent, v, w.Args[0], d, r)
		}
	}
}

var opMin = map[Op]int64{
	OpAdd64: math.MinInt64, OpSub64: math.MinInt64,
	OpAdd32: math.MinInt32, OpSub32: math.MinInt32,
}

var opMax = map[Op]int64{
	OpAdd64: math.MaxInt64, OpSub64: math.MaxInt64,
	OpAdd32: math.MaxInt32, OpSub32: math.MaxInt32,
}

var opUMax = map[Op]uint64{
	OpAdd64: math.MaxUint64, OpSub64: math.MaxUint64,
	OpAdd32: math.MaxUint32, OpSub32: math.MaxUint32,
}

// 非阴性报告是否已知v为非阴性。
func (ft *factsTable) isNonNegative(v *Value) bool {
	if isNonNegative(v) {
		return true
	}

	var max int64
	switch v.Type.Size() {
	case 1:
		max = math.MaxInt8
	case 2:
		max = math.MaxInt16
	case 4:
		max = math.MaxInt32
	case 8:
		max = math.MaxInt64
	default:
		panic("unexpected integer size")
	}

	// 检查记录的极限是否可以证明该值为正

	if l, has := ft.limits[v.ID]; has && (l.min >= 0 || l.umax <= uint64(max)) {
		return true
	}

	// 检查v=x+delta，我们可以使用x的极限来证明它为正
	if x, delta := isConstDelta(v); x != nil {
		if l, has := ft.limits[x.ID]; has {
			if delta > 0 && l.min >= -delta && l.max <= max-delta {
				return true
			}
			if delta < 0 && l.min >= -delta {
				return true
			}
		}
	}

	// 检查v是否是非负值的保值扩展。
	if isCleanExt(v) && ft.isNonNegative(v.Args[0]) {
		return true
	}

	// 检查签名的偏序集是否能证明值>=0 
	return ft.orderS.OrderedOrEqual(ft.zero, v)
}

// 检查点保存已知关系的当前状态。
// 在分支上下行时调用。
func (ft *factsTable) checkpoint() {
	if ft.unsat {
		ft.unsatDepth++
	}
	ft.stack = append(ft.stack, checkpointFact)
	ft.limitStack = append(ft.limitStack, checkpointBound)
	ft.orderS.Checkpoint()
	ft.orderU.Checkpoint()
}

// restore恢复与前一个检查点之前状态的已知关系。
// 备份分支时调用。
func (ft *factsTable) restore() {
	if ft.unsatDepth > 0 {
		ft.unsatDepth--
	} else {
		ft.unsat = false
	}
	for {
		old := ft.stack[len(ft.stack)-1]
		ft.stack = ft.stack[:len(ft.stack)-1]
		if old == checkpointFact {
			break
		}
		if old.r == lt|eq|gt {
			delete(ft.facts, old.p)
		} else {
			ft.facts[old.p] = old.r
		}
	}
	for {
		old := ft.limitStack[len(ft.limitStack)-1]
		ft.limitStack = ft.limitStack[:len(ft.limitStack)-1]
		if old.vid == 0 { // 检查点绑定
			break
		}
		if old.limit == noLimit {
			delete(ft.limits, old.vid)
		} else {
			ft.limits[old.vid] = old.limit
		}
	}
	ft.orderS.Undo()
	ft.orderU.Undo()
}

func lessByID(v, w *Value) bool {
	if v == nil && w == nil {
		// 不应该发生，只是以防万一。
		return false
	}
	if v == nil {
		return true
	}
	return w != nil && v.ID < w.ID
}

var (
	reverseBits = [...]relation{0, 4, 2, 6, 1, 5, 3, 7}

	// 映射我们在获得正分支时所学到的内容。
	// 例如：
	// OpLess8:{signed，lt}，
	// v1=（OpLess8 v2 v3）。
	// 如果采用v1分支，那么我们了解到rangeMask 
	// 最多只能是lt。
	domainRelationTable = map[Op]struct {
		d domain
		r relation
	}{
		OpEq8:   {signed | unsigned, eq},
		OpEq16:  {signed | unsigned, eq},
		OpEq32:  {signed | unsigned, eq},
		OpEq64:  {signed | unsigned, eq},
		OpEqPtr: {pointer, eq},

		OpNeq8:   {signed | unsigned, lt | gt},
		OpNeq16:  {signed | unsigned, lt | gt},
		OpNeq32:  {signed | unsigned, lt | gt},
		OpNeq64:  {signed | unsigned, lt | gt},
		OpNeqPtr: {pointer, lt | gt},

		OpLess8:   {signed, lt},
		OpLess8U:  {unsigned, lt},
		OpLess16:  {signed, lt},
		OpLess16U: {unsigned, lt},
		OpLess32:  {signed, lt},
		OpLess32U: {unsigned, lt},
		OpLess64:  {signed, lt},
		OpLess64U: {unsigned, lt},

		OpLeq8:   {signed, lt | eq},
		OpLeq8U:  {unsigned, lt | eq},
		OpLeq16:  {signed, lt | eq},
		OpLeq16U: {unsigned, lt | eq},
		OpLeq32:  {signed, lt | eq},
		OpLeq32U: {unsigned, lt | eq},
		OpLeq64:  {signed, lt | eq},
		OpLeq64U: {unsigned, lt | eq},

		// 对于这些操作，负分支是不同的：如果我们可以证明arg0是非负的，我们只能
		// 证明signed/GE（signed/GT）。
		// 请参阅addBranchRestrictions中的特殊情况。
		OpIsInBounds:      {signed | unsigned, lt},      // 0<=arg0<arg1 
		OpIsSliceInBounds: {signed | unsigned, lt | eq}, // 0<=arg0<=arg1 
	}
)

// cleanup将偏序集返回到自由列表
func (ft *factsTable) cleanup(f *Func) {
	for _, po := range []*poset{ft.orderS, ft.orderU} {
		// 确保其按原样为空。非空偏序集
		// 如果重复使用，可能会导致错误和错误编译。
		if checkEnabled {
			if err := po.CheckEmpty(); err != nil {
				f.Fatalf("poset not empty after function %s: %v", f.Name, err)
			}
		}
		f.retPoset(po)
	}
}

// prove删除了冗余的BlockIf分支，这些分支可以从之前的主要比较中推断出
// 。到目前为止，最常见的冗余对是通过边界检查生成的。
// 例如代码：
// 
// a[i]=4 
// foo（a[i]）
// 
// 编译器将生成以下代码：
// 
// panic（“not in bounds”）
// }
// foo（a[i]）
// 
// 。
// 第二次恐慌的代码可以删除。
// 
// 通过发现矛盾和修剪导致其状况无法满足的分支来证明作品。
// 它跟踪分支条件的“事实表”。对于每个分支
// 块，它断言唯一支配该
// 块的分支条件，然后分别断言该块的分支条件和
// 其否定。如果其中任何一个导致了矛盾，它可以削减
// 的继任者。
func prove(f *Func) {
	ft := newFactsTable(f)
	ft.checkpoint()

	var lensVars map[*Block][]*Value

	// 查找长度和容量操作。
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			if v.Uses == 0 {
				// 我们不在乎死价值观。
				// （可能有一些是CSEd，但尚未删除。）
				continue
			}
			switch v.Op {
			case OpStringLen:
				ft.update(b, v, ft.zero, signed, gt|eq)
			case OpSliceLen:
				if ft.lens == nil {
					ft.lens = map[ID]*Value{}
				}
				// 将同一片的所有len值设置为poset中的equal。
				// 偏序集处理传递关系，因此与
				// 此切片的任何操作切片相关的值都将正确地与其他操作切片相关。
				if l, ok := ft.lens[v.Args[0].ID]; ok {
					ft.update(b, v, l, signed, eq)
				} else {
					ft.lens[v.Args[0].ID] = v
				}
				ft.update(b, v, ft.zero, signed, gt|eq)
				if v.Args[0].Op == OpSliceMake {
					if lensVars == nil {
						lensVars = make(map[*Block][]*Value)
					}
					lensVars[b] = append(lensVars[b], v)
				}
			case OpSliceCap:
				if ft.caps == nil {
					ft.caps = map[ID]*Value{}
				}
				// 与上述案例OpSliceLen相同，但适用于切片帽。
				if c, ok := ft.caps[v.Args[0].ID]; ok {
					ft.update(b, v, c, signed, eq)
				} else {
					ft.caps[v.Args[0].ID] = v
				}
				ft.update(b, v, ft.zero, signed, gt|eq)
				if v.Args[0].Op == OpSliceMake {
					if lensVars == nil {
						lensVars = make(map[*Block][]*Value)
					}
					lensVars[b] = append(lensVars[b], v)
				}
			}
		}
	}

	// 查找归纳变量。目前，findIndVars 
	// 每个块仅限于一个感应变量。
	var indVars map[*Block]indVar
	for _, v := range findIndVar(f) {
		if indVars == nil {
			indVars = make(map[*Block]indVar)
		}
		indVars[v.entry] = v
	}

	// 当前节点状态
	type walkState int
	const (
		descend walkState = iota
		simplify
	)
	// work维护DFS堆栈。
	type bp struct {
		block *Block    // 当前处理的块
		state walkState // 该怎么做
	}
	work := make([]bp, 0, 256)
	work = append(work, bp{
		block: f.Entry,
		state: descend,
	})

	idom := f.Idom()
	sdom := f.Sdom()

	// 控制树上的DFS。ABCFDG 
	for len(work) > 0 {
		node := work[len(work)-1]
		work = work[:len(work)-1]
		parent := idom[node.block.ID]
		branch := getBranch(sdom, parent, node.block)

		switch node.state {
		case descend:
			ft.checkpoint()

			// 进入块，根据我们收集的事实添加块
			// 开始：诱导变量和切片的透镜/帽。
			if iv, ok := indVars[node.block]; ok {
				addIndVarRestrictions(ft, parent, iv)
			}
			if lens, ok := lensVars[node.block]; ok {
				for _, v := range lens {
					switch v.Op {
					case OpSliceLen:
						ft.update(node.block, v, v.Args[0].Args[1], signed, eq)
					case OpSliceCap:
						ft.update(node.block, v, v.Args[0].Args[2], signed, eq)
					}
				}
			}

			if branch != unknown {
				addBranchRestrictions(ft, parent, branch)
				if ft.unsat {
					// 节点。无法访问块。
					// 删除它，不要访问
					// 它的孩子。
					removeBranch(parent, branch)
					ft.restore()
					break
				}
				// 否则，我们现在可以向
				// 承诺接管该分支机构。我们将在放松时恢复
				// ft。
			}

			// 在此块中添加钓鱼的归纳事实。
			addLocalInductiveFacts(ft, node.block)

			work = append(work, bp{
				block: node.block,
				state: simplify,
			})
			for s := sdom.Child(node.block); s != nil; s = sdom.Sibling(s) {
				work = append(work, bp{
					block: s,
					state: descend,
				})
			}

		case simplify:
			simplifyBlock(sdom, ft, node.block)
			ft.restore()
		}
	}

	ft.restore()

	ft.cleanup(f)
}

// getBranch返回p 
// 到达b时添加的范围限制。p是b的直接支配者。
func getBranch(sdom SparseTree, p *Block, b *Block) branch {
	if p == nil || p.Kind != BlockIf {
		return unknown
	}
	// 如果p和p.Succs[0]是支配者，则表示从入口到b的每条路径
	// 都经过p和p.Succs[0]。我们关心的是
	// 从入口到b的路径没有经过p.Succs[1]。如果p.Succs[0]
	// 有一个前导，那么（除了退化的情况），
	// 没有从入口到b的路径可以通过p.Succs[1]。
	// TODO:p->yes->b->yes如何，即yes中的循环。
	if sdom.IsAncestorEq(p.Succs[0].b, b) && len(p.Succs[0].b.Preds) == 1 {
		return positive
	}
	if sdom.IsAncestorEq(p.Succs[1].b, b) && len(p.Succs[1].b.Preds) == 1 {
		return negative
	}
	return unknown
}

// addIndVarRestrictions用事实更新factsTables ft 
// 从驱动循环的归纳变量indVar学习
// 从块b开始。
func addIndVarRestrictions(ft *factsTable, b *Block, iv indVar) {
	d := signed
	if ft.isNonNegative(iv.min) && ft.isNonNegative(iv.max) {
		d |= unsigned
	}

	if iv.flags&indVarMinExc == 0 {
		addRestrictions(b, ft, d, iv.min, iv.ind, lt|eq)
	} else {
		addRestrictions(b, ft, d, iv.min, iv.ind, lt)
	}

	if iv.flags&indVarMaxInc == 0 {
		addRestrictions(b, ft, d, iv.ind, iv.max, lt)
	} else {
		addRestrictions(b, ft, d, iv.ind, iv.max, lt|eq)
	}
}

// addBranchRestrictions用
// 从块b向方向分支时学习的事实更新factsTables ft。
func addBranchRestrictions(ft *factsTable, b *Block, br branch) {
	c := b.Controls[0]
	switch br {
	case negative:
		addRestrictions(b, ft, boolean, nil, c, eq)
	case positive:
		addRestrictions(b, ft, boolean, nil, c, lt|gt)
	default:
		panic("unknown branch")
	}
	if tr, has := domainRelationTable[c.Op]; has {
		// 当我们从父母那里分支时，我们学到了一套新的
		// 限制。相应地更新factsTable。
		d := tr.d
		if d == signed && ft.isNonNegative(c.Args[0]) && ft.isNonNegative(c.Args[1]) {
			d |= unsigned
		}
		switch c.Op {
		case OpIsInBounds, OpIsSliceInBounds:
			// 0<=a0<a1（或0<=a0<=a1）
			// 
			// 在正向分支上，我们了解到：
			// 签名：0<=a0<a1（或0<=a0<=a1）
			// unsigned:a0<a1（或a0<=a1）
			// 
			// 在负分支上，我们学习（0>a0 | | 
			// a0>=a1）。在unsigned domain中，这是
			// 简单地说是a0>=a1（这是
			// 正分支的反面，所以没什么奇怪的）。
			// 但是在签名域中，我们不能表达| | 
			// 条件，所以检查a0是否为非负，
			// 以便能够学习一些东西。
			switch br {
			case negative:
				d = unsigned
				if ft.isNonNegative(c.Args[0]) {
					d |= signed
				}
				addRestrictions(b, ft, d, c.Args[0], c.Args[1], tr.r^(lt|gt|eq))
			case positive:
				addRestrictions(b, ft, signed, ft.zero, c.Args[0], lt|eq)
				addRestrictions(b, ft, d, c.Args[0], c.Args[1], tr.r)
			}
		default:
			switch br {
			case negative:
				addRestrictions(b, ft, d, c.Args[0], c.Args[1], tr.r^(lt|gt|eq))
			case positive:
				addRestrictions(b, ft, d, c.Args[0], c.Args[1], tr.r)
			}
		}

	}
}

// addRestrictions使用r更新直接
// 支配块（p）中的限制。
func addRestrictions(parent *Block, ft *factsTable, t domain, v, w *Value, r relation) {
	if t == 0 {
		// 无关紧要的情况：无事可做。不应该发生，只是以防万一。
		return
	}
	for i := domain(1); i <= t; i <<= 1 {
		if t&i == 0 {
			continue
		}
		ft.update(parent, v, w, i, r)
	}
}

// addLocaligenductiveFacts在访问b时添加归纳事实，其中
// b是循环中的连接点。与findIndVar相反，这个
// 取决于为b建立的事实，这就是为什么访问b时会发生
// 的原因。AddLocalInductionFacts专门针对OfRuntil创建的模式
// ，findIndVar没有检测到该模式。
// 
// TODO:将此与findIndVar相结合会很好。
func addLocalInductiveFacts(ft *factsTable, b *Block) {
	// 这寻找一种特定的归纳模式：
	// 
	// 1。i1=OpPhi（最小值，i2）在b 
	// 2中。i2=i1+1 
	// 3。i2<b.Preds[1]
	// 4退出时的最大值。min<max 
	// 
	// 如果所有这些条件都为真，那么i1<max和i1>=min.

	// 以确保这是一个循环头节点。
	if len(b.Preds) != 2 {
		return
	}

	for _, i1 := range b.Values {
		if i1.Op != OpPhi {
			continue
		}

		// 检查条件1和2。这很容易做到
		// 并且将丢弃大多数网络钓鱼。
		min, i2 := i1.Args[0], i1.Args[1]
		if i1q, delta := isConstDelta(i2); i1q != i1 || delta != 1 {
			continue
		}

		// 尝试证明条件3。我们不能只查询
		// 事实表，因为我们不知道b.Preds[1]的事实是什么（一般来说，b.Preds[1]是
		// 一个循环回边，所以我们甚至还没有到过那里）。作为保守近似，我们在前导链中寻找
		// 这个条件，直到我们到达一个连接点。
		uniquePred := func(b *Block) *Block {
			if len(b.Preds) == 1 {
				return b.Preds[0].b
			}
			return nil
		}
		pred, child := b.Preds[1].b, b
		for ; pred != nil; pred, child = uniquePred(pred), pred {
			if pred.Kind != BlockIf {
				continue
			}
			control := pred.Controls[0]

			br := unknown
			if pred.Succs[0].b == child {
				br = positive
			}
			if pred.Succs[1].b == child {
				if br != unknown {
					continue
				}
				br = negative
			}
			if br == unknown {
				continue
			}

			tr, has := domainRelationTable[control.Op]
			if !has {
				continue
			}
			r := tr.r
			if br == negative {
				// 到达b的负分支。
				// 补充关系。
				r = (lt | eq | gt) ^ r
			}

			// 检查i2<max或max>i2。
			var max *Value
			if r == lt && control.Args[0] == i2 {
				max = control.Args[1]
			} else if r == gt && control.Args[1] == i2 {
				max = control.Args[0]
			} else {
				continue
			}

			// 检查条件4，现在我们有了一个
			// 候选最大值。为此，我们可以查询
			// 事实表。我们通过显示
			// 证明min>=max是未满足的，从而“证明”min<max。（这可能只是
			// 比较两个常数，没关系。）
			ft.checkpoint()
			ft.update(b, min, max, tr.d, gt|eq)
			proved := ft.unsat
			ft.restore()

			if proved {
				// 我们知道min<=i1<max.
				if b.Func.pass.debug > 0 {
					printIndVar(b, i1, min, max, 1, 0)
				}
				ft.update(b, min, i1, tr.d, lt|eq)
				ft.update(b, i1, max, tr.d, lt)
			}
		}
	}
}

var ctzNonZeroOp = map[Op]Op{OpCtz8: OpCtz8NonZero, OpCtz16: OpCtz16NonZero, OpCtz32: OpCtz32NonZero, OpCtz64: OpCtz64NonZero}
var mostNegativeDividend = map[Op]int64{
	OpDiv16: -1 << 15,
	OpMod16: -1 << 15,
	OpDiv32: -1 << 31,
	OpMod32: -1 << 31,
	OpDiv64: -1 << 63,
	OpMod64: -1 << 63}

// simplifyBlock简化了b中的一些常量值，并计算了
// 分支到b的非唯一支配后继者。
func simplifyBlock(sdom SparseTree, ft *factsTable, b *Block) {
	for _, v := range b.Values {
		switch v.Op {
		case OpSlicemask:
			// 尽可能用常量替换b中的OpSlicemask操作。
			x, delta := isConstDelta(v.Args[0])
			if x == nil {
				continue
			}
			// 切片掩码（x+y）
			// 如果x大于-y（y为负），则切片掩码为-1。
			lim, ok := ft.limits[x.ID]
			if !ok {
				continue
			}
			if lim.umin > uint64(-delta) {
				if v.Args[0].Op == OpAdd64 {
					v.reset(OpConst64)
				} else {
					v.reset(OpConst32)
				}
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved slicemask not needed")
				}
				v.AuxInt = -1
			}
		case OpCtz8, OpCtz16, OpCtz32, OpCtz64:
			// 在某些体系结构上，尤其是在amd64上，如果我们知道参数非零，我们可以为CtzNN生成更好的代码。
			// 在此处捕获这些信息，以用于特定于arch的优化。
			x := v.Args[0]
			lim, ok := ft.limits[x.ID]
			if !ok {
				continue
			}
			if lim.umin > 0 || lim.min > 0 || lim.max < 0 {
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved %v non-zero", v.Op)
				}
				v.Op = ctzNonZeroOp[v.Op]
			}
		case OpRsh8x8, OpRsh8x16, OpRsh8x32, OpRsh8x64,
			OpRsh16x8, OpRsh16x16, OpRsh16x32, OpRsh16x64,
			OpRsh32x8, OpRsh32x16, OpRsh32x32, OpRsh32x64,
			OpRsh64x8, OpRsh64x16, OpRsh64x32, OpRsh64x64:
			// 检查对于a>>b，我们是否知道a是非负的
			// 并且b是a的所有位，除了MSB。如果是这样，a将被移到零。
			bits := 8 * v.Type.Size()
			if v.Args[1].isGenericIntConst() && v.Args[1].AuxInt >= bits-1 && ft.isNonNegative(v.Args[0]) {
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved %v shifts to zero", v.Op)
				}
				switch bits {
				case 64:
					v.reset(OpConst64)
				case 32:
					v.reset(OpConst32)
				case 16:
					v.reset(OpConst16)
				case 8:
					v.reset(OpConst8)
				default:
					panic("unexpected integer size")
				}
				v.AuxInt = 0
				continue // 一定不要犯错误——这不再是一种错误。
			}
			// 如果Rsh没有被0替换，仍然检查它是否有界。
			fallthrough
		case OpLsh8x8, OpLsh8x16, OpLsh8x32, OpLsh8x64,
			OpLsh16x8, OpLsh16x16, OpLsh16x32, OpLsh16x64,
			OpLsh32x8, OpLsh32x16, OpLsh32x32, OpLsh32x64,
			OpLsh64x8, OpLsh64x16, OpLsh64x32, OpLsh64x64,
			OpRsh8Ux8, OpRsh8Ux16, OpRsh8Ux32, OpRsh8Ux64,
			OpRsh16Ux8, OpRsh16Ux16, OpRsh16Ux32, OpRsh16Ux64,
			OpRsh32Ux8, OpRsh32Ux16, OpRsh32Ux32, OpRsh32Ux64,
			OpRsh64Ux8, OpRsh64Ux16, OpRsh64Ux32, OpRsh64Ux64:
			// 检查对于a<<b，我们是否知道b 
			// 严格小于a中的位数。
			by := v.Args[1]
			lim, ok := ft.limits[by.ID]
			if !ok {
				continue
			}
			bits := 8 * v.Args[0].Type.Size()
			if lim.umax < uint64(bits) || (lim.max < bits && ft.isNonNegative(by)) {
				v.AuxInt = 1 // 请参阅amd64和386上的移位有界
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved %v bounded", v.Op)
				}
			}
		case OpDiv16, OpDiv32, OpDiv64, OpMod16, OpMod32, OpMod64:
			// 如果我们知道
			// 除数不是-1或股息>MinIntNN，则可以避免使用修复代码。
			// 不要在其他架构上修改生长素，因为这可能会干扰CSE。
			// 待办事项：添加其他体系结构？
			if b.Func.Config.arch != "386" && b.Func.Config.arch != "amd64" {
				break
			}
			divr := v.Args[1]
			divrLim, divrLimok := ft.limits[divr.ID]
			divd := v.Args[0]
			divdLim, divdLimok := ft.limits[divd.ID]
			if (divrLimok && (divrLim.max < -1 || divrLim.min > -1)) ||
				(divdLimok && divdLim.min > mostNegativeDividend[v.Op]) {
				// 请参阅“重写”中的分区需求修复。去
				// v.AuxInt=1意味着我们已经证明除数不是-1 
				// 并且被除数不是最负的整数，因此我们不需要添加修复代码。ABCFDG 
				v.AuxInt = 1
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(v.Pos, "Proved %v does not need fix-up", v.Op)
				}
			}
		}
	}

	if b.Kind != BlockIf {
		return
	}

	parent := b
	for i, branch := range [...]branch{positive, negative} {
		child := parent.Succs[i].b
		if getBranch(sdom, parent, child) != unknown {
			// 对于唯一支配块的边缘，我们在拜访孩子时已经这样做了。
			continue
		}
		// 对于其他块的边，这可以修剪分支
		// 即使我们无法摆脱孩子本身。
		ft.checkpoint()
		addBranchRestrictions(ft, parent, branch)
		unsat := ft.unsat
		ft.restore()
		if unsat {
			// 这个分支是不可能的，所以将其从块中删除
			// 。
			removeBranch(parent, branch)
			// 没有必要考虑其他分支。
			// （由于事实表
			// 不完整，两者都有可能无法满足。我们可以将其转换为
			// 块退出，但这似乎不值得。）
			break
		}
	}
}

func removeBranch(b *Block, branch branch) {
	c := b.Controls[0]
	if b.Func.pass.debug > 0 {
		verb := "Proved"
		if branch == positive {
			verb = "Disproved"
		}
		if b.Func.pass.debug > 1 {
			b.Func.Warnl(b.Pos, "%s %s (%s)", verb, c.Op, c)
		} else {
			b.Func.Warnl(b.Pos, "%s %s", verb, c.Op)
		}
	}
	if c != nil && c.Pos.IsStmt() == src.PosIsStmt && c.Pos.SameFileAndLine(b.Pos) {
		// 尝试保留语句标记。
		b.Pos = b.Pos.WithIsStmt()
	}
	b.Kind = BlockFirst
	b.ResetControls()
	if branch == positive {
		b.swapSuccessors()
	}
}

// 非负报告v是否大于或等于零。
func isNonNegative(v *Value) bool {
	if !v.Type.IsInteger() {
		v.Fatalf("isNonNegative bad type: %v", v.Type)
	}
	// TODO:如果返回true！v、 打字。IsSigned（）
	// SSA的类型安全性还不够，现在无法做到这一点（第37753期）。
	// 下面的检查仅取决于位的模式。

	switch v.Op {
	case OpConst64:
		return v.AuxInt >= 0

	case OpConst32:
		return int32(v.AuxInt) >= 0

	case OpConst16:
		return int16(v.AuxInt) >= 0

	case OpConst8:
		return int8(v.AuxInt) >= 0

	case OpStringLen, OpSliceLen, OpSliceCap,
		OpZeroExt8to64, OpZeroExt16to64, OpZeroExt32to64,
		OpZeroExt8to32, OpZeroExt16to32, OpZeroExt8to16,
		OpCtz64, OpCtz32, OpCtz16, OpCtz8:
		return true

	case OpRsh64Ux64, OpRsh32Ux64:
		by := v.Args[1]
		return by.Op == OpConst64 && by.AuxInt > 0

	case OpRsh64x64, OpRsh32x64, OpRsh8x64, OpRsh16x64, OpRsh32x32, OpRsh64x32,
		OpSignExt32to64, OpSignExt16to64, OpSignExt8to64, OpSignExt16to32, OpSignExt8to32:
		return isNonNegative(v.Args[0])

	case OpAnd64, OpAnd32, OpAnd16, OpAnd8:
		return isNonNegative(v.Args[0]) || isNonNegative(v.Args[1])

	case OpMod64, OpMod32, OpMod16, OpMod8,
		OpDiv64, OpDiv32, OpDiv16, OpDiv8,
		OpOr64, OpOr32, OpOr16, OpOr8,
		OpXor64, OpXor32, OpXor16, OpXor8:
		return isNonNegative(v.Args[0]) && isNonNegative(v.Args[1])

		// 我们可以在这里处理OpPhi，但是做
		// 的改进非常小，既不简单也不便宜。
	}
	return false
}

// 如果v等于w+delta（有符号），isConstDelta返回非nil。
func isConstDelta(v *Value) (w *Value, delta int64) {
	cop := OpConst64
	switch v.Op {
	case OpAdd32, OpSub32:
		cop = OpConst32
	}
	switch v.Op {
	case OpAdd64, OpAdd32:
		if v.Args[0].Op == cop {
			return v.Args[1], v.Args[0].AuxInt
		}
		if v.Args[1].Op == cop {
			return v.Args[0], v.Args[1].AuxInt
		}
	case OpSub64, OpSub32:
		if v.Args[1].Op == cop {
			aux := v.Args[1].AuxInt
			if aux != -aux { // 溢出；太糟糕了
				return v.Args[0], -aux
			}
		}
	}
	return nil, 0
}

// isCleanExt报告v是否是保值
// 符号或零扩展
func isCleanExt(v *Value) bool {
	switch v.Op {
	case OpSignExt8to16, OpSignExt8to32, OpSignExt8to64,
		OpSignExt16to32, OpSignExt16to64, OpSignExt32to64:
		// 已签名->已签名是唯一的保值符号扩展
		return v.Args[0].Type.IsSigned() && v.Type.IsSigned()

	case OpZeroExt8to16, OpZeroExt8to32, OpZeroExt8to64,
		OpZeroExt16to32, OpZeroExt16to64, OpZeroExt32to64:
		// 未签名->已签名/未签名是保值零扩展
		return !v.Args[0].Type.IsSigned()
	}
	return false
}
